/**
 * 迭代
 * @param {ListNode} head
 * @return {ListNode}
 */
let reverseList = function (head) {
    let result = null

    while (head) {
        let tempNext = head.next
        head.next = result

        // 保存当前已迭代反转的结果
        result = head
        // 重置当前未迭代反转的链
        head = tempNext
    }

    return result
};

/**
 * 递归
 * @param {ListNode} head
 * @return {ListNode}
 */
let reverseList2 = function (head) {
    if (head === null || head.next === null) {
        return head
    }
    let newHead = reverseList(head.next)      // 唯一的newHead和head的关联，newHead = head.next
    // head：5>7 newHead：7           第一次往上递归
    // head：4>5 newHead：7>5           第二次往上递归
    head.next.next = head     // 此时是一个环
    head.next = null     
    //head:5 newHead:7>5   head.next传进来的时候是5>7，这时只剩5了， 一次往上递归后，head本来是4>5>7，变成了4>5
    //head:4 newHead:7>5>4    第二次往上递归
    return newHead
};

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
}

let l1 = new ListNode(1)
l1.next = new ListNode(4)
l1.next.next = new ListNode(5)
l1.next.next.next = new ListNode(7)
